﻿#define _CRT_SECURE_NO_WARNINGS 1
//给你一个链表的头节点 head 和一个整数 val ，请你删除链表中所有满足 Node.val == val 的节点，并返回 新的头节点 。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//typedef struct ListNode ListNode;
//struct ListNode* removeElements(struct ListNode* head, int val) {
//    // 创建新链表
//    ListNode* NewTail, * NewHead;
//    NewHead = NewTail = NULL;
//    // 遍历原链表
//    ListNode* pcur = head;
//    while (pcur)
//    {
//        if (pcur->val != val)
//        {
//            // 链表为空
//            if (NewHead == NULL)
//            {
//                NewHead = NewTail = pcur;
//            }
//            else
//            {
//                NewTail->next = pcur;
//                NewTail = NewTail->next;
//            }
//        }
//        pcur = pcur->next;
//    }
//    if (NewTail)
//        NewTail->next = NULL;
//    return NewHead;
//}


//给你单链表的头节点 head ，请你反转链表，并返回反转后的链表。
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode ListNode;
//struct ListNode* reverseList(struct ListNode* head) {
//    ListNode* n1, * n2, * n3;
//    if (head == NULL)
//        return head;
//    n1 = NULL;
//    n2 = head;
//    n3 = n2->next;
//    while (n2)
//    {
//        n2->next = n1;
//        n1 = n2;
//        n2 = n3;
//        if (n3)
//            n3 = n3->next;
//    }
//    return n1;
//}


//给你单链表的头结点 head ，请你找出并返回链表的中间结点。
//
//如果有两个中间结点，则返回第二个中间结点。
/////**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode ListNode;
//struct ListNode* middleNode(struct ListNode* head) {
//    ListNode* fast, * slow;
//    fast = slow = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//    }
//    return slow;
//}

//将两个升序链表合并为一个新的 升序 链表并返回。新链表是通过拼接给定的两个链表的所有节点组成的。
//typedef struct ListNode ListNode;
//struct ListNode* mergeTwoLists(struct ListNode* list1, struct ListNode* list2) {
//    ListNode* NewHead = NULL, * NewTail = NULL;
//    if (list1 == NULL)
//        return list2;
//    if (list2 == NULL)
//        return list1;
//    while (list1 && list2)
//    {
//        if (list1->val > list2->val)
//        {
//            if (NewHead == NULL)
//            {
//                NewHead = NewTail = list2;
//            }
//            else
//            {
//                NewTail->next = list2;
//                NewTail = NewTail->next;
//            }
//            list2 = list2->next;
//        }
//        else
//        {
//            if (NewHead == NULL)
//            {
//                NewHead = NewTail = list1;
//            }
//            else
//            {
//                NewTail->next = list1;
//                NewTail = NewTail->next;
//            }
//            list1 = list1->next;
//        }
//    }
//    while (list1)
//    {
//        NewTail->next = list1;
//        NewTail = NewTail->next;
//        list1 = list1->next;
//    }
//    while (list2)
//    {
//        NewTail->next = list2;
//        NewTail = NewTail->next;
//        list2 = list2->next;
//    }
//    return NewHead;
//}


//描述
//现有一链表的头指针 ListNode* pHead，给一定值x，编写一段代码将所有小于x的结点排在其余结点之前，且不能改变原来的数据顺序，返回重新排列后的链表的头指针。
///*
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};*/
//#include <cstddef>
//class Partition {
//public:
//    ListNode* partition(ListNode* pHead, int x) {
//        // write code here
//        //创建两个非空链表
//        ListNode* LessHead, * LessTail, * GreatHead, * GreatTail;
//        LessHead = LessTail = (ListNode*)malloc(sizeof(ListNode));
//        GreatHead = GreatTail = (ListNode*)malloc(sizeof(ListNode));
//        while (pHead)
//        {
//            if (pHead->val < x)
//            {
//                LessTail->next = pHead;
//                LessTail = LessTail->next;
//            }
//            else
//            {
//                GreatTail->next = pHead;
//                GreatTail = GreatTail->next;
//            }
//            pHead = pHead->next;
//        }
//        LessTail->next = GreatHead->next;
//        GreatTail->next = NULL;
//        ListNode* ret = LessHead->next;
//        free(GreatHead);
//        GreatHead = NULL;
//        free(LessHead);
//        LessHead = NULL;
//        return ret;
//    }
//};

//对于一个链表，请设计一个时间复杂度为O(n), 额外空间复杂度为O(1)的算法，判断其是否为回文结构。
//
//给定一个链表的头指针A，请返回一个bool值，代表其是否为回文结构。保证链表长度小于等于900。
//
//测试样例：
///*
//struct ListNode {
//    int val;
//    struct ListNode *next;
//    ListNode(int x) : val(x), next(NULL) {}
//};*/
//class PalindromeList {
//public:
//    bool chkPalindrome(ListNode* A) {
//        // write code here
//        …{
//                 rightmid = i / 2;
//                 leftmid = i / 2 - 1;
//        }
//        else {
//            rightmid = leftmid = i / 2;
//        }
//        while (leftmid > -1 && rightmid < i)
//        {
//            if (arr[leftmid] == arr[rightmid])
//            {
//                leftmid--;
//                rightmid++;
//            }
//            else {
//                return false;
//            }
//        }
//        return true;
//    }
//};


//给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode ListNode;
//struct ListNode* getIntersectionNode(struct ListNode* headA, struct ListNode* headB) {
//    size_t a, b;
//    a = b = 0;
//    ListNode* l1, * l2;
//    l1 = headA;
//    l2 = headB;
//    while (l1)
//    {
//        l1 = l1->next;
//        a++;
//    }
//    while (l2)
//    {
//        l2 = l2->next;
//        b++;
//    }
//    int gap = abs(a - b);
//    ListNode* longlist, * shortlist;
//    longlist = headA;
//    shortlist = headB;
//    if (a < b)
//    {
//        longlist = headB;
//        shortlist = headA;
//    }
//    while (gap--)
//    {
//        longlist = longlist->next;
//    }
//    while(longlist&&shortlist)
//{
//    if (longlist == shortlist)
//        return longlist;
//    longlist = longlist->next;
//    shortlist = shortlist->next;
//    }
//    return NULL;
//}

//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。
//
//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
//
//不允许修改 链表。
///**
// * Definition for singly-linked list.
// * struct ListNode {
// *     int val;
// *     struct ListNode *next;
// * };
// */
//typedef struct ListNode ListNode;
//struct ListNode* detectCycle(struct ListNode* head) {
//    ListNode* slow, fast;
//    slow = fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//            return true;
//    }
//    return false;
//}


//给定一个链表的头节点  head ，返回链表开始入环的第一个节点。 如果链表无环，则返回 null。

//如果链表中有某个节点，可以通过连续跟踪 next 指针再次到达，则链表中存在环。 为了表示给定链表中的环，评测系统内部使用整数 pos 来表示链表尾连接到链表中的位置（索引从 0 开始）。如果 pos 是 - 1，则在该链表中没有环。注意：pos 不作为参数进行传递，仅仅是为了标识链表的实际情况。
/**
 * Definition for singly-linked list.
 * struct ListNode {
 *     int val;
 *     struct ListNode *next;
 * };
 */
//typedef struct ListNode ListNode;
//struct ListNode* detectCycle(struct ListNode* head) {
//    ListNode* slow, * fast, * meet;
//    meet = NULL;
//    slow = fast = head;
//    while (fast && fast->next)
//    {
//        slow = slow->next;
//        fast = fast->next->next;
//        if (fast == slow)
//        {
//            ListNode* pcur = fast;
//            while (pcur != head)
//            {
//                pcur = pcur->next;
//                head = head->next;
//            }
//            return pcur;
//        }
//    }
//    return NULL;
//}



//给你一个长度为 n 的链表，每个节点包含一个额外增加的随机指针 random ，该指针可以指向链表中的任何节点或空节点。
//
//构造这个链表的 深拷贝。 深拷贝应该正好由 n 个 全新 节点组成，其中每个新节点的值都设为其对应的原节点的值。新节点的 next 指针和 random 指针也都应指向复制链表中的新节点，并使原链表和复制链表中的这些指针能够表示相同的链表状态。复制链表中的指针都不应指向原链表中的节点 。
//
//例如，如果原链表中有 X 和 Y 两个节点，其中 X.random-- > Y 。那么在复制链表中对应的两个节点 x 和 y ，同样有 x.random-- > y 。
//
//返回复制链表的头节点。
//
//用一个由 n 个节点组成的链表来表示输入 / 输出中的链表。每个节点用一个 [val, random_index] 表示：
//
//val：一个表示 Node.val 的整数。
//random_index：随机指针指向的节点索引（范围从 0 到 n - 1）；如果不指向任何节点，则为  null 。
//你的代码 只 接受原链表的头节点 head 作为传入参数。
/**
 * Definition for a Node.
 * struct Node {
 *     int val;
 *     struct Node *next;
 *     struct Node *random;
 * };
 */
//typedef struct Node Node;
//Node* BuyNode(int x)
//{
//    Node* NewNode = (Node*)malloc(sizeof(Node));
//    NewNode->val = x;
//    NewNode->next = NewNode->random = NULL;
//
//    return NewNode;
//
//}
//
//void AddNode(Node* head)
//{
//    Node* pcur = head;
//    while (pcur)
//    {
//        Node* next = pcur->next;
//        Node* NewNode = BuyNode(pcur->val);
//        pcur->next = NewNode;
//        NewNode->next = next;
//        pcur = next;
//    }
//}
//struct Node* copyRandomList(struct Node* head) {
//    if (head == NULL)
//        return NULL;
//    AddNode(head);
//    Node* pcur = head;
//    while (pcur)
//    {
//        Node* copy = pcur->next;
//        if (pcur->random != NULL)
//        {
//            copy->random = pcur->random->next;
//        }
//        pcur = copy->next;
//    }
//    pcur = head;
//    Node* NewHead, * NewTail;
//    NewHead = NewTail = pcur->next;
//    while (pcur->next->next)
//    {
//        pcur = pcur->next->next;
//        NewTail->next = pcur->next;
//        NewTail = NewTail->next;
//    }
//    return NewHead;
//}